Backtracking

Table of Contents

1. Backtracking Template
2. Pattern 1: Subset Generation
3. Pattern 2: Permutation Generation
4. Pattern 3: Combination Problems
5. Pattern 4: Partition Problems
6. Pattern 5: Grid/Matrix Traversal
7. Pattern 6: N-Queens & Placement Problems
8. Pattern 7: Word Search & Trie Problems
9. Pattern 8: Expression & Equation Problems
10. Pattern 9: Game & Puzzle Problems
11. Pattern 10: Tree Traversal Backtracking
12. Pattern 11: Advanced Constraint Problems
13. Pattern 12: Optimization Problems

---

Backtracking Template

Core Template Structure

// Universal Backtracking Template
void backtrack(List<List<Integer>> result, List<Integer> current,
               int[] nums, int start) {
    // Base case: check if solution is complete
    if (isComplete(current)) {
        result.add(new ArrayList<>(current)); // Make copy
        return;
    }

    // Iterate through all possible choices from current state
    for (int i = start; i < nums.length; i++) {
        // Skip invalid choices (pruning)
        if (!isValid(current, nums[i])) continue;

        // Make choice
        current.add(nums[i]);

        // Recurse with choice made
        backtrack(result, current, nums, i + 1);

        // Undo choice (backtrack)
        current.remove(current.size() - 1);
    }
}

// Helper methods
boolean isComplete(List<Integer> current) {
    // Define completion condition
    return current.size() == targetSize;
}

boolean isValid(List<Integer> current, int candidate) {
    // Define validity constraints
    return true; // Implement specific logic
}

Key Components

class BacktrackingFramework {
    // 1. State representation
    List<Integer> currentPath = new ArrayList<>();

    // 2. Result collection
    List<List<Integer>> allSolutions = new ArrayList<>();

    // 3. Choice exploration
    void explore(int[] choices, int index) {
        // Base case
        if (isGoalReached()) {
            processSolution();
            return;
        }

        // Try all valid choices
        for (int i = index; i < choices.length; i++) {
            if (isValidChoice(choices[i])) {
                makeChoice(choices[i]);      // Choose
                explore(choices, i + 1);     // Explore
                undoChoice();                // Unchoose
            }
        }
    }

    boolean isGoalReached() { return /* condition */; }
    boolean isValidChoice(int choice) { return /* validation */; }
    void makeChoice(int choice) { currentPath.add(choice); }
    void undoChoice() { currentPath.remove(currentPath.size() - 1); }
    void processSolution() { allSolutions.add(new ArrayList<>(currentPath)); }
}

---

Pattern 1: Subset Generation

1.1 Generate All Subsets

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackSubsets(result, new ArrayList<>(), nums, 0);
    return result;
}

void backtrackSubsets(List<List<Integer>> result, List<Integer> current,
                     int[] nums, int start) {
    // Every recursive call represents a valid subset
    result.add(new ArrayList<>(current));

    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        backtrackSubsets(result, current, nums, i + 1);
        current.remove(current.size() - 1);
    }
}

1.2 Subsets II (With Duplicates)

List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums); // Sort to handle duplicates
    List<List<Integer>> result = new ArrayList<>();
    backtrackSubsetsDup(result, new ArrayList<>(), nums, 0);
    return result;
}

void backtrackSubsetsDup(List<List<Integer>> result, List<Integer> current,
                        int[] nums, int start) {
    result.add(new ArrayList<>(current));

    for (int i = start; i < nums.length; i++) {
        // Skip duplicates: only process first occurrence at each level
        if (i > start && nums[i] == nums[i - 1]) continue;

        current.add(nums[i]);
        backtrackSubsetsDup(result, current, nums, i + 1);
        current.remove(current.size() - 1);
    }
}

1.3 Subset Sum Problem

List<List<Integer>> subsetSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    backtrackSum(result, new ArrayList<>(), nums, target, 0);
    return result;
}

void backtrackSum(List<List<Integer>> result, List<Integer> current,
                 int[] nums, int remaining, int start) {
    if (remaining == 0) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i < nums.length; i++) {
        if (nums[i] > remaining) break; // Pruning: sorted array
        if (i > start && nums[i] == nums[i - 1]) continue; // Skip duplicates

        current.add(nums[i]);
        backtrackSum(result, current, nums, remaining - nums[i], i + 1);
        current.remove(current.size() - 1);
    }
}

1.4 Power Set (Iterative Approach)

List<List<Integer>> powerSet(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>()); // Empty subset

    for (int num : nums) {
        int size = result.size();
        for (int i = 0; i < size; i++) {
            List<Integer> subset = new ArrayList<>(result.get(i));
            subset.add(num);
            result.add(subset);
        }
    }

    return result;
}

1.5 Generate Subsets by Size

List<List<Integer>> subsetsBySize(int[] nums, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackBySize(result, new ArrayList<>(), nums, k, 0);
    return result;
}

void backtrackBySize(List<List<Integer>> result, List<Integer> current,
                    int[] nums, int k, int start) {
    if (current.size() == k) {
        result.add(new ArrayList<>(current));
        return;
    }

    // Optimization: ensure enough elements remain
    int needed = k - current.size();
    int available = nums.length - start;
    if (available < needed) return;

    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        backtrackBySize(result, current, nums, k, i + 1);
        current.remove(current.size() - 1);
    }
}

---

Pattern 2: Permutation Generation

2.1 Generate All Permutations

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackPermute(result, new ArrayList<>(), nums);
    return result;
}

void backtrackPermute(List<List<Integer>> result, List<Integer> current, int[] nums) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int num : nums) {
        if (current.contains(num)) continue; // Skip used elements

        current.add(num);
        backtrackPermute(result, current, nums);
        current.remove(current.size() - 1);
    }
}

// Optimized version using boolean array
List<List<Integer>> permuteOptimized(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrackPermuteOpt(result, new ArrayList<>(), nums, used);
    return result;
}

void backtrackPermuteOpt(List<List<Integer>> result, List<Integer> current,
                        int[] nums, boolean[] used) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        used[i] = true;
        current.add(nums[i]);
        backtrackPermuteOpt(result, current, nums, used);
        current.remove(current.size() - 1);
        used[i] = false;
    }
}

2.2 Permutations II (With Duplicates)

List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums); // Sort to handle duplicates
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrackPermuteDup(result, new ArrayList<>(), nums, used);
    return result;
}

void backtrackPermuteDup(List<List<Integer>> result, List<Integer> current,
                        int[] nums, boolean[] used) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        // Skip duplicates: use first occurrence in sorted order
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

        used[i] = true;
        current.add(nums[i]);
        backtrackPermuteDup(result, current, nums, used);
        current.remove(current.size() - 1);
        used[i] = false;
    }
}

2.3 Next Permutation

void nextPermutation(int[] nums) {
    int i = nums.length - 2;

    // Find first decreasing element from right
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    if (i >= 0) {
        int j = nums.length - 1;
        // Find element just larger than nums[i]
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);
    }

    // Reverse suffix
    reverse(nums, i + 1);
}

void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void reverse(int[] nums, int start) {
    int end = nums.length - 1;
    while (start < end) {
        swap(nums, start++, end--);
    }
}

2.4 Permutation Sequence (Kth Permutation)

String getPermutation(int n, int k) {
    List<Integer> numbers = new ArrayList<>();
    int[] factorial = new int[n + 1];

    // Calculate factorials and build number list
    factorial[^3_0] = 1;
    for (int i = 1; i <= n; i++) {
        factorial[i] = factorial[i - 1] * i;
        numbers.add(i);
    }

    k--; // Convert to 0-based indexing
    StringBuilder result = new StringBuilder();

    for (int i = n; i > 0; i--) {
        int index = k / factorial[i - 1];
        result.append(numbers.get(index));
        numbers.remove(index);
        k %= factorial[i - 1];
    }

    return result.toString();
}

2.5 String Permutations

List<String> stringPermutations(String s) {
    List<String> result = new ArrayList<>();
    char[] chars = s.toCharArray();
    Arrays.sort(chars); // Handle duplicates
    boolean[] used = new boolean[chars.length];
    backtrackStringPerm(result, new StringBuilder(), chars, used);
    return result;
}

void backtrackStringPerm(List<String> result, StringBuilder current,
                        char[] chars, boolean[] used) {
    if (current.length() == chars.length) {
        result.add(current.toString());
        return;
    }

    for (int i = 0; i < chars.length; i++) {
        if (used[i]) continue;
        if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) continue;

        used[i] = true;
        current.append(chars[i]);
        backtrackStringPerm(result, current, chars, used);
        current.deleteCharAt(current.length() - 1);
        used[i] = false;
    }
}

---

Pattern 3: Combination Problems

3.1 Generate Combinations

List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackCombine(result, new ArrayList<>(), 1, n, k);
    return result;
}

void backtrackCombine(List<List<Integer>> result, List<Integer> current,
                     int start, int n, int k) {
    if (current.size() == k) {
        result.add(new ArrayList<>(current));
        return;
    }

    // Optimization: check if enough numbers remain
    int needed = k - current.size();
    int available = n - start + 1;
    if (available < needed) return;

    for (int i = start; i <= n; i++) {
        current.add(i);
        backtrackCombine(result, current, i + 1, n, k);
        current.remove(current.size() - 1);
    }
}

3.2 Combination Sum

List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);
    backtrackCombSum(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

void backtrackCombSum(List<List<Integer>> result, List<Integer> current,
                     int[] candidates, int remaining, int start) {
    if (remaining == 0) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remaining) break; // Pruning

        current.add(candidates[i]);
        // Allow reuse of same element: pass i instead of i+1
        backtrackCombSum(result, current, candidates, remaining - candidates[i], i);
        current.remove(current.size() - 1);
    }
}

3.3 Combination Sum II (No Reuse)

List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> result = new ArrayList<>();
    backtrackCombSum2(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

void backtrackCombSum2(List<List<Integer>> result, List<Integer> current,
                      int[] candidates, int remaining, int start) {
    if (remaining == 0) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remaining) break;
        if (i > start && candidates[i] == candidates[i - 1]) continue;

        current.add(candidates[i]);
        backtrackCombSum2(result, current, candidates, remaining - candidates[i], i + 1);
        current.remove(current.size() - 1);
    }
}

3.4 Letter Combinations of Phone Number

List<String> letterCombinations(String digits) {
    if (digits.isEmpty()) return new ArrayList<>();

    String[] mapping = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };

    List<String> result = new ArrayList<>();
    backtrackLetters(result, new StringBuilder(), digits, mapping, 0);
    return result;
}

void backtrackLetters(List<String> result, StringBuilder current,
                     String digits, String[] mapping, int index) {
    if (index == digits.length()) {
        result.add(current.toString());
        return;
    }

    String letters = mapping[digits.charAt(index) - '0'];
    for (char letter : letters.toCharArray()) {
        current.append(letter);
        backtrackLetters(result, current, digits, mapping, index + 1);
        current.deleteCharAt(current.length() - 1);
    }
}

3.5 Generate Parentheses

List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrackParentheses(result, new StringBuilder(), 0, 0, n);
    return result;
}

void backtrackParentheses(List<String> result, StringBuilder current,
                         int open, int close, int max) {
    if (current.length() == max * 2) {
        result.add(current.toString());
        return;
    }

    if (open < max) {
        current.append('(');
        backtrackParentheses(result, current, open + 1, close, max);
        current.deleteCharAt(current.length() - 1);
    }

    if (close < open) {
        current.append(')');
        backtrackParentheses(result, current, open, close + 1, max);
        current.deleteCharAt(current.length() - 1);
    }
}

---

Pattern 4: Partition Problems

4.1 Palindrome Partitioning

List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    backtrackPartition(result, new ArrayList<>(), s, 0);
    return result;
}

void backtrackPartition(List<List<String>> result, List<String> current,
                       String s, int start) {
    if (start == s.length()) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int end = start; end < s.length(); end++) {
        if (isPalindrome(s, start, end)) {
            current.add(s.substring(start, end + 1));
            backtrackPartition(result, current, s, end + 1);
            current.remove(current.size() - 1);
        }
    }
}

boolean isPalindrome(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--)) {
            return false;
        }
    }
    return true;
}

4.2 Word Break II

List<String> wordBreak(String s, List<String> wordDict) {
    Set<String> wordSet = new HashSet<>(wordDict);
    List<String> result = new ArrayList<>();
    backtrackWordBreak(result, new ArrayList<>(), s, wordSet, 0);
    return result;
}

void backtrackWordBreak(List<String> result, List<String> current,
                       String s, Set<String> wordSet, int start) {
    if (start == s.length()) {
        result.add(String.join(" ", current));
        return;
    }

    for (int end = start + 1; end <= s.length(); end++) {
        String word = s.substring(start, end);
        if (wordSet.contains(word)) {
            current.add(word);
            backtrackWordBreak(result, current, s, wordSet, end);
            current.remove(current.size() - 1);
        }
    }
}

4.3 Restore IP Addresses

List<String> restoreIpAddresses(String s) {
    List<String> result = new ArrayList<>();
    backtrackIP(result, new ArrayList<>(), s, 0);
    return result;
}

void backtrackIP(List<String> result, List<String> current,
                String s, int start) {
    if (current.size() == 4) {
        if (start == s.length()) {
            result.add(String.join(".", current));
        }
        return;
    }

    for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
        String segment = s.substring(start, start + len);
        if (isValidIPSegment(segment)) {
            current.add(segment);
            backtrackIP(result, current, s, start + len);
            current.remove(current.size() - 1);
        }
    }
}

boolean isValidIPSegment(String segment) {
    if (segment.length() > 1 && segment.charAt(0) == '0') return false;
    int num = Integer.parseInt(segment);
    return num >= 0 && num <= 255;
}

4.4 Partition to K Equal Sum Subsets

boolean canPartitionKSubsets(int[] nums, int k) {
    int sum = Arrays.stream(nums).sum();
    if (sum % k != 0) return false;

    int target = sum / k;
    Arrays.sort(nums);

    // Start from largest number for better pruning
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }

    return backtrackPartitionK(nums, new int[k], 0, target);
}

boolean backtrackPartitionK(int[] nums, int[] buckets, int index, int target) {
    if (index == nums.length) {
        for (int bucket : buckets) {
            if (bucket != target) return false;
        }
        return true;
    }

    for (int i = 0; i < buckets.length; i++) {
        if (buckets[i] + nums[index] <= target) {
            buckets[i] += nums[index];
            if (backtrackPartitionK(nums, buckets, index + 1, target)) {
                return true;
            }
            buckets[i] -= nums[index];

            // Pruning: if current bucket is empty, no need to try other empty buckets
            if (buckets[i] == 0) break;
        }
    }

    return false;
}

---

Pattern 5: Grid/Matrix Traversal

5.1 Word Search in Grid

boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[^3_0].length; j++) {
            if (dfsWordSearch(board, word, i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

boolean dfsWordSearch(char[][] board, String word, int i, int j, int index) {
    if (index == word.length()) return true;

    if (i < 0 || i >= board.length || j < 0 || j >= board[^3_0].length ||
        board[i][j] != word.charAt(index)) {
        return false;
    }

    char temp = board[i][j];
    board[i][j] = '#'; // Mark as visited

    boolean found = dfsWordSearch(board, word, i + 1, j, index + 1) ||
                   dfsWordSearch(board, word, i - 1, j, index + 1) ||
                   dfsWordSearch(board, word, i, j + 1, index + 1) ||
                   dfsWordSearch(board, word, i, j - 1, index + 1);

    board[i][j] = temp; // Backtrack
    return found;
}

5.2 Number of Islands

int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;

    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[^3_0].length; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfsIsland(grid, i, j);
            }
        }
    }
    return count;
}

void dfsIsland(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[^3_0].length ||
        grid[i][j] != '1') {
        return;
    }

    grid[i][j] = '0'; // Mark as visited

    dfsIsland(grid, i + 1, j);
    dfsIsland(grid, i - 1, j);
    dfsIsland(grid, i, j + 1);
    dfsIsland(grid, i, j - 1);
}

5.3 Surrounded Regions

void solve(char[][] board) {
    if (board == null || board.length == 0) return;

    int m = board.length, n = board[^3_0].length;

    // Mark boundary-connected 'O's
    for (int i = 0; i < m; i++) {
        if (board[i][^3_0] == 'O') dfsFlip(board, i, 0);
        if (board[i][n - 1] == 'O') dfsFlip(board, i, n - 1);
    }

    for (int j = 0; j < n; j++) {
        if (board[^3_0][j] == 'O') dfsFlip(board, 0, j);
        if (board[m - 1][j] == 'O') dfsFlip(board, m - 1, j);
    }

    // Flip remaining 'O's to 'X' and restore marked ones
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] == '#') {
                board[i][j] = 'O';
            }
        }
    }
}

void dfsFlip(char[][] board, int i, int j) {
    if (i < 0 || i >= board.length || j < 0 || j >= board[^3_0].length ||
        board[i][j] != 'O') {
        return;
    }

    board[i][j] = '#'; // Temporary mark

    dfsFlip(board, i + 1, j);
    dfsFlip(board, i - 1, j);
    dfsFlip(board, i, j + 1);
    dfsFlip(board, i, j - 1);
}

5.4 Path with Maximum Gold

int getMaximumGold(int[][] grid) {
    int maxGold = 0;

    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[^3_0].length; j++) {
            if (grid[i][j] != 0) {
                maxGold = Math.max(maxGold, dfsGold(grid, i, j));
            }
        }
    }

    return maxGold;
}

int dfsGold(int[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[^3_0].length ||
        grid[i][j] == 0) {
        return 0;
    }

    int gold = grid[i][j];
    grid[i][j] = 0; // Mark as visited

    int maxPath = Math.max(
        Math.max(dfsGold(grid, i + 1, j), dfsGold(grid, i - 1, j)),
        Math.max(dfsGold(grid, i, j + 1), dfsGold(grid, i, j - 1))
    );

    grid[i][j] = gold; // Backtrack
    return gold + maxPath;
}

5.5 Unique Paths III

int uniquePathsIII(int[][] grid) {
    int startX = 0, startY = 0, empty = 1; // Count starting square as empty

    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[^3_0].length; j++) {
            if (grid[i][j] == 1) {
                startX = i;
                startY = j;
            } else if (grid[i][j] == 0) {
                empty++;
            }
        }
    }

    return dfsUniquePaths(grid, startX, startY, empty);
}

int dfsUniquePaths(int[][] grid, int x, int y, int empty) {
    if (x < 0 || x >= grid.length || y < 0 || y >= grid[^3_0].length ||
        grid[x][y] == -1) {
        return 0;
    }

    if (grid[x][y] == 2) {
        return empty == 0 ? 1 : 0; // Reached end, check if all squares visited
    }

    grid[x][y] = -1; // Mark as visited
    int paths = dfsUniquePaths(grid, x + 1, y, empty - 1) +
               dfsUniquePaths(grid, x - 1, y, empty - 1) +
               dfsUniquePaths(grid, x, y + 1, empty - 1) +
               dfsUniquePaths(grid, x, y - 1, empty - 1);

    grid[x][y] = 0; // Backtrack
    return paths;
}

---

Pattern 6: N-Queens & Placement Problems

6.1 N-Queens Problem

List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];

    // Initialize board
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');
    }

    backtrackNQueens(result, board, 0);
    return result;
}

void backtrackNQueens(List<List<String>> result, char[][] board, int row) {
    if (row == board.length) {
        result.add(constructBoard(board));
        return;
    }

    for (int col = 0; col < board.length; col++) {
        if (isValidPlacement(board, row, col)) {
            board[row][col] = 'Q';
            backtrackNQueens(result, board, row + 1);
            board[row][col] = '.';
        }
    }
}

boolean isValidPlacement(char[][] board, int row, int col) {
    int n = board.length;

    // Check column
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }

    // Check diagonal (top-left to bottom-right)
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }

    // Check anti-diagonal (top-right to bottom-left)
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }

    return true;
}

List<String> constructBoard(char[][] board) {
    List<String> result = new ArrayList<>();
    for (char[] row : board) {
        result.add(new String(row));
    }
    return result;
}

6.2 N-Queens II (Count Solutions)

int totalNQueens(int n) {
    return backtrackCountQueens(n, 0, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
}

int backtrackCountQueens(int n, int row, boolean[] cols, boolean[] diag1, boolean[] diag2) {
    if (row == n) return 1;

    int count = 0;
    for (int col = 0; col < n; col++) {
        int d1 = row - col + n, d2 = row + col;

        if (!cols[col] && !diag1[d1] && !diag2[d2]) {
            cols[col] = diag1[d1] = diag2[d2] = true;
            count += backtrackCountQueens(n, row + 1, cols, diag1, diag2);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }

    return count;
}

6.3 Sudoku Solver

void solveSudoku(char[][] board) {
    backtrackSudoku(board);
}

boolean backtrackSudoku(char[][] board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                for (char c = '1'; c <= '9'; c++) {
                    if (isValidSudoku(board, i, j, c)) {
                        board[i][j] = c;

                        if (backtrackSudoku(board)) {
                            return true;
                        }

                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}

boolean isValidSudoku(char[][] board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        // Check row
        if (board[row][i] == c) return false;

        // Check column
        if (board[i][col] == c) return false;

        // Check 3x3 box
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
            return false;
        }
    }
    return true;
}

6.4 Knight's Tour Problem

boolean knightTour(int n) {
    int[][] board = new int[n][n];
    int[] xMoves = {2, 1, -1, -2, -2, -1, 1, 2};
    int[] yMoves = {1, 2, 2, 1, -1, -2, -2, -1};

    // Initialize all squares as unvisited
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], -1);
    }

    board[^3_0][^3_0] = 0; // Starting position
    return backtrackKnight(board, 0, 0, 1, xMoves, yMoves, n);
}

boolean backtrackKnight(int[][] board, int x, int y, int moveCount,
                       int[] xMoves, int[] yMoves, int n) {
    if (moveCount == n * n) return true;

    for (int i = 0; i < 8; i++) {
        int nextX = x + xMoves[i];
        int nextY = y + yMoves[i];

        if (isValidKnightMove(board, nextX, nextY, n)) {
            board[nextX][nextY] = moveCount;

            if (backtrackKnight(board, nextX, nextY, moveCount + 1, xMoves, yMoves, n)) {
                return true;
            }

            board[nextX][nextY] = -1; // Backtrack
        }
    }

    return false;
}

boolean isValidKnightMove(int[][] board, int x, int y, int n) {
    return x >= 0 && x < n && y >= 0 && y < n && board[x][y] == -1;
}

---

Pattern 7: Word Search & Trie Problems

7.1 Word Search II

class TrieNode {
    TrieNode[] children = new TrieNode[^3_26];
    String word;
}

List<String> findWords(char[][] board, String[] words) {
    TrieNode root = buildTrie(words);
    List<String> result = new ArrayList<>();

    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[^3_0].length; j++) {
            dfsWordSearch(board, i, j, root, result);
        }
    }

    return result;
}

TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String word : words) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
        curr.word = word;
    }
    return root;
}

void dfsWordSearch(char[][] board, int i, int j, TrieNode node, List<String> result) {
    if (i < 0 || i >= board.length || j < 0 || j >= board[^3_0].length) return;

    char c = board[i][j];
    if (c == '#' || node.children[c - 'a'] == null) return;

    node = node.children[c - 'a'];
    if (node.word != null) {
        result.add(node.word);
        node.word = null; // Avoid duplicates
    }

    board[i][j] = '#'; // Mark as visited
    dfsWordSearch(board, i + 1, j, node, result);
    dfsWordSearch(board, i - 1, j, node, result);
    dfsWordSearch(board, i, j + 1, node, result);
    dfsWordSearch(board, i, j - 1, node, result);
    board[i][j] = c; // Backtrack
}

7.2 Boggle Game

List<String> findWordsInBoggle(char[][] board, String[] dictionary) {
    TrieNode root = buildTrie(dictionary);
    Set<String> result = new HashSet<>();
    boolean[][] visited = new boolean[board.length][board[^3_0].length];

    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[^3_0].length; j++) {
            dfsBoggle(board, i, j, root, "", visited, result);
        }
    }

    return new ArrayList<>(result);
}

void dfsBoggle(char[][] board, int i, int j, TrieNode node, String word,
              boolean[][] visited, Set<String> result) {
    if (i < 0 || i >= board.length || j < 0 || j >= board[^3_0].length ||
        visited[i][j]) {
        return;
    }

    char c = board[i][j];
    if (node.children[c - 'a'] == null) return;

    word += c;
    node = node.children[c - 'a'];

    if (node.word != null) {
        result.add(word);
    }

    visited[i][j] = true;

    // Explore all 8 directions
    int[][] directions = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};
    for (int[] dir : directions) {
        dfsBoggle(board, i + dir[^3_0], j + dir[^3_1], node, word, visited, result);
    }

    visited[i][j] = false; // Backtrack
}

---

Pattern 8: Expression & Equation Problems

8.1 Expression Add Operators

List<String> addOperators(String num, int target) {
    List<String> result = new ArrayList<>();
    backtrackOperators(result, "", num, target, 0, 0, 0);
    return result;
}

void backtrackOperators(List<String> result, String expr, String num, int target,
                       int index, long eval, long mult) {
    if (index == num.length()) {
        if (eval == target) {
            result.add(expr);
        }
        return;
    }

    for (int i = index; i < num.length(); i++) {
        String curr = num.substring(index, i + 1);

        // Skip numbers with leading zeros (except single '0')
        if (curr.length() > 1 && curr.charAt(0) == '0') break;

        long currNum = Long.parseLong(curr);

        if (index == 0) {
            backtrackOperators(result, curr, num, target, i + 1, currNum, currNum);
        } else {
            // Addition
            backtrackOperators(result, expr + "+" + curr, num, target,
                             i + 1, eval + currNum, currNum);

            // Subtraction
            backtrackOperators(result, expr + "-" + curr, num, target,
                             i + 1, eval - currNum, -currNum);

            // Multiplication (handle precedence)
            backtrackOperators(result, expr + "*" + curr, num, target,
                             i + 1, eval - mult + mult * currNum, mult * currNum);
        }
    }
}

8.2 Different Ways to Add Parentheses

List<Integer> diffWaysToCompute(String expression) {
    List<Integer> result = new ArrayList<>();

    for (int i = 0; i < expression.length(); i++) {
        char c = expression.charAt(i);

        if (c == '+' || c == '-' || c == '*') {
            List<Integer> left = diffWaysToCompute(expression.substring(0, i));
            List<Integer> right = diffWaysToCompute(expression.substring(i + 1));

            for (int l : left) {
                for (int r : right) {
                    if (c == '+') {
                        result.add(l + r);
                    } else if (c == '-') {
                        result.add(l - r);
                    } else if (c == '*') {
                        result.add(l * r);
                    }
                }
            }
        }
    }

    // Base case: single number
    if (result.isEmpty()) {
        result.add(Integer.parseInt(expression));
    }

    return result;
}

8.3 24 Game

boolean judgePoint24(int[] nums) {
    List<Double> list = new ArrayList<>();
    for (int num : nums) {
        list.add((double) num);
    }
    return backtrack24Game(list);
}

boolean backtrack24Game(List<Double> nums) {
    if (nums.size() == 1) {
        return Math.abs(nums.get(0) - 24.0) < 1e-6;
    }

    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            double a = nums.get(i);
            double b = nums.get(j);

            List<Double> next = new ArrayList<>();
            for (int k = 0; k < nums.size(); k++) {
                if (k != i && k != j) {
                    next.add(nums.get(k));
                }
            }

            // Try all operations
            for (double c : compute(a, b)) {
                next.add(c);
                if (backtrack24Game(next)) {
                    return true;
                }
                next.remove(next.size() - 1);
            }
        }
    }

    return false;
}

List<Double> compute(double a, double b) {
    List<Double> results = new ArrayList<>();
    results.add(a + b);
    results.add(a - b);
    results.add(b - a);
    results.add(a * b);
    if (Math.abs(b) > 1e-6) results.add(a / b);
    if (Math.abs(a) > 1e-6) results.add(b / a);
    return results;
}

---

Pattern 9: Game & Puzzle Problems

9.1 Tic-Tac-Toe AI (Minimax with Backtracking)

class TicTacToe {
    char[][] board = new char[^3_3][^3_3];

    int minimax(boolean isMaximizing) {
        int score = evaluate();

        if (score == 10) return score;  // X wins
        if (score == -10) return score; // O wins
        if (!isMovesLeft()) return 0;   // Tie

        if (isMaximizing) {
            int best = -1000;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (board[i][j] == ' ') {
                        board[i][j] = 'X';
                        best = Math.max(best, minimax(false));
                        board[i][j] = ' '; // Backtrack
                    }
                }
            }
            return best;
        } else {
            int best = 1000;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (board[i][j] == ' ') {
                        board[i][j] = 'O';
                        best = Math.min(best, minimax(true));
                        board[i][j] = ' '; // Backtrack
                    }
                }
            }
            return best;
        }
    }

    int[] findBestMove() {
        int bestVal = -1000;
        int[] bestMove = {-1, -1};

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == ' ') {
                    board[i][j] = 'X';
                    int moveVal = minimax(false);
                    board[i][j] = ' '; // Backtrack

                    if (moveVal > bestVal) {
                        bestMove[^3_0] = i;
                        bestMove[^3_1] = j;
                        bestVal = moveVal;
                    }
                }
            }
        }

        return bestMove;
    }

    int evaluate() {
        // Check rows, columns, and diagonals
        for (int row = 0; row < 3; row++) {
            if (board[row][^3_0] == board[row][^3_1] && board[row][^3_1] == board[row][^3_2]) {
                if (board[row][^3_0] == 'X') return 10;
                else if (board[row][^3_0] == 'O') return -10;
            }
        }

        for (int col = 0; col < 3; col++) {
            if (board[^3_0][col] == board[^3_1][col] && board[^3_1][col] == board[^3_2][col]) {
                if (board[^3_0][col] == 'X') return 10;
                else if (board[^3_0][col] == 'O') return -10;
            }
        }

        if (board[^3_0][^3_0] == board[^3_1][^3_1] && board[^3_1][^3_1] == board[^3_2][^3_2]) {
            if (board[^3_0][^3_0] == 'X') return 10;
            else if (board[^3_0][^3_0] == 'O') return -10;
        }

        if (board[^3_0][^3_2] == board[^3_1][^3_1] && board[^3_1][^3_1] == board[^3_2][^3_0]) {
            if (board[^3_0][^3_2] == 'X') return 10;
            else if (board[^3_0][^3_2] == 'O') return -10;
        }

        return 0;
    }

    boolean isMovesLeft() {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == ' ') return true;
            }
        }
        return false;
    }
}

9.2 Word Ladder with Backtracking

List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return new ArrayList<>();

    Map<String, List<String>> neighbors = new HashMap<>();
    Map<String, Integer> distance = new HashMap<>();

    bfsWordLadder(beginWord, endWord, wordSet, neighbors, distance);

    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    path.add(beginWord);

    dfsWordLadder(beginWord, endWord, neighbors, distance, path, result);
    return result;
}

void bfsWordLadder(String beginWord, String endWord, Set<String> wordSet,
                  Map<String, List<String>> neighbors, Map<String, Integer> distance) {
    for (String word : wordSet) {
        neighbors.put(word, new ArrayList<>());
    }
    neighbors.put(beginWord, new ArrayList<>());

    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    distance.put(beginWord, 0);

    while (!queue.isEmpty()) {
        boolean found = false;
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            String word = queue.poll();
            int curDist = distance.get(word);

            List<String> nextWords = getNextWords(word, wordSet);
            for (String nextWord : nextWords) {
                neighbors.get(word).add(nextWord);

                if (!distance.containsKey(nextWord)) {
                    distance.put(nextWord, curDist + 1);
                    if (nextWord.equals(endWord)) {
                        found = true;
                    } else {
                        queue.offer(nextWord);
                    }
                }
            }
        }

        if (found) break;
    }
}

void dfsWordLadder(String word, String endWord, Map<String, List<String>> neighbors,
                  Map<String, Integer> distance, List<String> path, List<List<String>> result) {
    if (word.equals(endWord)) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (String neighbor : neighbors.get(word)) {
        if (distance.get(neighbor) == distance.get(word) + 1) {
            path.add(neighbor);
            dfsWordLadder(neighbor, endWord, neighbors, distance, path, result);
            path.remove(path.size() - 1);
        }
    }
}

List<String> getNextWords(String word, Set<String> wordSet) {
    List<String> nextWords = new ArrayList<>();
    char[] chars = word.toCharArray();

    for (int i = 0; i < chars.length; i++) {
        char temp = chars[i];
        for (char c = 'a'; c <= 'z'; c++) {
            chars[i] = c;
            String newWord = new String(chars);
            if (wordSet.contains(newWord) && !newWord.equals(word)) {
                nextWords.add(newWord);
            }
        }
        chars[i] = temp;
    }

    return nextWords;
}

---

Pattern 10: Tree Traversal Backtracking

10.1 Binary Tree Paths

List<String> binaryTreePaths(TreeNode root) {
    List<String> result = new ArrayList<>();
    if (root != null) {
        backtrackTreePaths(root, "", result);
    }
    return result;
}

void backtrackTreePaths(TreeNode node, String path, List<String> result) {
    if (node.left == null && node.right == null) {
        result.add(path + node.val);
        return;
    }

    if (node.left != null) {
        backtrackTreePaths(node.left, path + node.val + "->", result);
    }

    if (node.right != null) {
        backtrackTreePaths(node.right, path + node.val + "->", result);
    }
}

10.2 Path Sum II

List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackPathSum(root, targetSum, new ArrayList<>(), result);
    return result;
}

void backtrackPathSum(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> result) {
    if (node == null) return;

    path.add(node.val);

    if (node.left == null && node.right == null && remaining == node.val) {
        result.add(new ArrayList<>(path));
    } else {
        backtrackPathSum(node.left, remaining - node.val, path, result);
        backtrackPathSum(node.right, remaining - node.val, path, result);
    }

    path.remove(path.size() - 1); // Backtrack
}

10.3 Sum Root to Leaf Numbers

int sumNumbers(TreeNode root) {
    return backtrackSumNumbers(root, 0);
}

int backtrackSumNumbers(TreeNode node, int currentSum) {
    if (node == null) return 0;

    currentSum = currentSum * 10 + node.val;

    if (node.left == null && node.right == null) {
        return currentSum;
    }

    return backtrackSumNumbers(node.left, currentSum) +
           backtrackSumNumbers(node.right, currentSum);
}

---

Pattern 11: Advanced Constraint Problems

11.1 Graph Coloring

boolean graphColoring(int[][] graph, int m) {
    int n = graph.length;
    int[] colors = new int[n];
    return backtrackColoring(graph, colors, 0, m);
}

boolean backtrackColoring(int[][] graph, int[] colors, int vertex, int m) {
    if (vertex == graph.length) return true;

    for (int color = 1; color <= m; color++) {
        if (isSafeColoring(graph, colors, vertex, color)) {
            colors[vertex] = color;

            if (backtrackColoring(graph, colors, vertex + 1, m)) {
                return true;
            }

            colors[vertex] = 0; // Backtrack
        }
    }

    return false;
}

boolean isSafeColoring(int[][] graph, int[] colors, int vertex, int color) {
    for (int i = 0; i < graph.length; i++) {
        if (graph[vertex][i] == 1 && colors[i] == color) {
            return false;
        }
    }
    return true;
}

11.2 Hamiltonian Path

boolean hamiltonianPath(int[][] graph) {
    int n = graph.length;
    int[] path = new int[n];
    Arrays.fill(path, -1);

    // Try starting from each vertex
    for (int start = 0; start < n; start++) {
        path[^3_0] = start;
        if (backtrackHamiltonian(graph, path, 1)) {
            return true;
        }
    }

    return false;
}

boolean backtrackHamiltonian(int[][] graph, int[] path, int pos) {
    if (pos == graph.length) return true;

    for (int v = 0; v < graph.length; v++) {
        if (isSafeHamiltonian(graph, path, pos, v)) {
            path[pos] = v;

            if (backtrackHamiltonian(graph, path, pos + 1)) {
                return true;
            }

            path[pos] = -1; // Backtrack
        }
    }

    return false;
}

boolean isSafeHamiltonian(int[][] graph, int[] path, int pos, int v) {
    // Check if vertex is adjacent to previous vertex
    if (graph[path[pos - 1]][v] == 0) return false;

    // Check if vertex is already included in path
    for (int i = 0; i < pos; i++) {
        if (path[i] == v) return false;
    }

    return true;
}

---

Pattern 12: Optimization Problems

12.1 Minimum Cost Path with Backtracking

int minCostPath(int[][] grid) {
    int m = grid.length, n = grid[^3_0].length;
    return backtrackMinCost(grid, 0, 0, m - 1, n - 1);
}

int backtrackMinCost(int[][] grid, int x, int y, int targetX, int targetY) {
    if (x == targetX && y == targetY) {
        return grid[x][y];
    }

    if (x > targetX || y > targetY) {
        return Integer.MAX_VALUE;
    }

    int rightCost = backtrackMinCost(grid, x, y + 1, targetX, targetY);
    int downCost = backtrackMinCost(grid, x + 1, y, targetX, targetY);

    return grid[x][y] + Math.min(rightCost, downCost);
}

12.2 Maximum Path Sum with Constraints

int maxPathSum(int[][] grid, int maxSteps) {
    boolean[][] visited = new boolean[grid.length][grid[^3_0].length];
    return backtrackMaxPath(grid, 0, 0, visited, maxSteps);
}

int backtrackMaxPath(int[][] grid, int x, int y, boolean[][] visited, int stepsLeft) {
    if (x < 0 || x >= grid.length || y < 0 || y >= grid[^3_0].length ||
        visited[x][y] || stepsLeft < 0) {
        return Integer.MIN_VALUE;
    }

    if (stepsLeft == 0) {
        return grid[x][y];
    }

    visited[x][y] = true;

    int maxSum = grid[x][y];
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    int pathMax = Integer.MIN_VALUE;
    for (int i = 0; i < 4; i++) {
        int nextSum = backtrackMaxPath(grid, x + dx[i], y + dy[i], visited, stepsLeft - 1);
        if (nextSum != Integer.MIN_VALUE) {
            pathMax = Math.max(pathMax, nextSum);
        }
    }

    visited[x][y] = false; // Backtrack

    return pathMax == Integer.MIN_VALUE ? Integer.MIN_VALUE : maxSum + pathMax;
}

---

Time Complexity Analysis

Pattern	Time Complexity	Space Complexity	Use Cases
Subsets	O(2^n)	O(n)	Power set generation
Permutations	O(n!)	O(n)	Arrangement problems
Combinations	O(C(n,k))	O(k)	Selection problems
N-Queens	O(N!)	O(N)	Constraint satisfaction
Sudoku	O(9^(n*n))	O(n*n)	Puzzle solving
Word Search	O(4^L)	O(L)	Grid traversal
Expression Parsing	O(4^n)	O(n)	Math expressions

---

Common Optimization Techniques

Pruning Strategies

1. Early Termination: Stop when constraints violated
2. Bound Checking: Use upper/lower bounds to prune
3. Symmetry Breaking: Avoid duplicate computations
4. Constraint Propagation: Forward checking validity
5. Memoization: Cache intermediate results when possible

Template Optimizations

// Optimized backtracking with pruning
void optimizedBacktrack(int[] nums, List<Integer> current, int start, int target) {
    // Early termination
    if (getCurrentSum(current) > target) return;

    // Bound checking
    if (current.size() + (nums.length - start) < minRequiredSize) return;

    // Goal check
    if (isGoalReached(current, target)) {
        processResult(current);
        return;
    }

    for (int i = start; i < nums.length; i++) {
        // Skip duplicates
        if (i > start && nums[i] == nums[i-1]) continue;

        // Validity check before recursion
        if (isValidChoice(current, nums[i])) {
            current.add(nums[i]);
            optimizedBacktrack(nums, current, i + 1, target);
            current.remove(current.size() - 1);
        }
    }
}

---

Interview Tips & Best Practices

Problem Recognition

1. Generate all possibilities: Use backtracking
2. Find one solution: Often backtracking with early return
3. Count solutions: Backtracking with counter
4. Optimize solution: Add pruning and memoization

Implementation Strategy

1. Draw the decision tree first[^3_2]
2. Identify the choices at each step
3. Define base cases clearly
4. Implement choice, explore, unchoose pattern
5. Add pruning for optimization

Common Mistakes to Avoid

• Forgetting to make a copy when adding to results
• Not handling duplicates properly in sorted arrays
• Missing backtracking (unchoose) step
• Incorrect base case conditions
• Not using visited arrays for grid problems